{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Moves to Make Array Complementary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组互补的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为<strong> 偶数</strong> <code>n</code> 的整数数组 <code>nums</code> 和一个整数 <code>limit</code> 。每一次操作，你可以将 <code>nums</code> 中的任何整数替换为 <code>1</code> 到 <code>limit</code> 之间的另一个整数。</p>\n",
    "\n",
    "<p>如果对于所有下标 <code>i</code>（<strong>下标从 </strong><code>0</code><strong> 开始</strong>），<code>nums[i] + nums[n - 1 - i]</code> 都等于同一个数，则数组 <code>nums</code> 是 <strong>互补的</strong> 。例如，数组 <code>[1,2,3,4]</code> 是互补的，因为对于所有下标 <code>i</code> ，<code>nums[i] + nums[n - 1 - i] = 5</code> 。</p>\n",
    "\n",
    "<p>返回使数组 <strong>互补</strong> 的 <strong>最少</strong> 操作次数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4,3], limit = 4\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>经过 1 次操作，你可以将数组 nums 变成 [1,2,<strong>2</strong>,3]（加粗元素是变更的数字）：\n",
    "nums[0] + nums[3] = 1 + 3 = 4.\n",
    "nums[1] + nums[2] = 2 + 2 = 4.\n",
    "nums[2] + nums[1] = 2 + 2 = 4.\n",
    "nums[3] + nums[0] = 3 + 1 = 4.\n",
    "对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2,1], limit = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>经过 2 次操作，你可以将数组 nums 变成 [<strong>2</strong>,2,2,<strong>2</strong>] 。你不能将任何数字变更为 3 ，因为 3 > limit 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,1,2], limit = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>nums 已经是互补的。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= limit <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n</code> 是偶数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-moves-to-make-array-complementary](https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-moves-to-make-array-complementary](https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4,3]\\n4', '[1,2,2,1]\\n2', '[1,2,1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for i in nums:\n",
    "            count+=abs(i-nums[len(nums)//2])\n",
    "\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        mid = len(nums) // 2\n",
    "\n",
    "        result = 0\n",
    "\n",
    "# 每个数和中位数的差的和\n",
    "\n",
    "        for j in nums:\n",
    "\n",
    "            result += abs(j-nums[mid])\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mid = len(nums) // 2\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans += abs(nums[i] - nums[mid])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        aver = nums[n >> 1]\n",
    "        return sum(abs(i - aver) for i in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        aver = nums[n >> 1]\n",
    "        return sum(abs(i - aver) for i in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        medium_num = self.KthNumber(nums, n//2)\n",
    "        print(medium_num)\n",
    "        move = 0\n",
    "        for num in nums:\n",
    "            move += abs(num-medium_num)\n",
    "        return move\n",
    "\n",
    "\n",
    "    def KthNumber(self, nums, k):\n",
    "        def partion(l, r):\n",
    "            if l>=r:\n",
    "                return l\n",
    "            i, j = l, r\n",
    "            dummy = nums[l]\n",
    "            while i<j:\n",
    "                while i<j and nums[j] >= dummy:\n",
    "                    j -= 1\n",
    "                nums[i] = nums[j]\n",
    "                while i<j and nums[i] < dummy:\n",
    "                    i += 1\n",
    "                nums[j] = nums[i]\n",
    "            nums[i] = dummy\n",
    "            return i\n",
    "        \n",
    "        l, r = 0, len(nums)-1\n",
    "        while l<r:\n",
    "            mid = partion(l, r)\n",
    "            if mid == k:\n",
    "                break\n",
    "            elif mid < k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return nums[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        nums.sort()\n",
    "        i,j=0,len(nums)-1\n",
    "        while i<j:\n",
    "            cnt+=nums[j]-nums[i]\n",
    "            i+=1\n",
    "            j-=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=nums[len(nums)//2]\n",
    "        return sum([abs(x-n) for x in nums])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        temp1 = int(statistics.median(nums))\n",
    "        print(help(median))\n",
    "        temp2 = temp1 + 1\n",
    "        ans1 = 0\n",
    "        ans2 = 0\n",
    "        for num in nums:\n",
    "            ans1 += abs(num - temp1)\n",
    "            ans2 += abs(num - temp2)\n",
    "\n",
    "        return min(ans1, ans2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        heap = [i for i in nums]\n",
    "        heapq.heapify(heap)\n",
    "        mid = heap[0]\n",
    "        for _ in range(len(heap)//2+1):\n",
    "            mid = heapq.heappop(heap)\n",
    "        return sum([abs(i-mid) for i in nums])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        a = [0] * l\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                continue\n",
    "            else:\n",
    "                a[i] = (a[i-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * l\n",
    "        ans = inf\n",
    "        for i in range(l-2, -1, -1):\n",
    "            before = l - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "            ans = min(ans, b[i] + a[i])\n",
    "\n",
    "        # ans = inf\n",
    "        # for i in range(l):\n",
    "        #     ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums = [x - nums[0] for x in nums]\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # print(nums)\n",
    "        # print(s)\n",
    "        n = len(nums)\n",
    "        return s[n] - s[n//2] * 2 - nums[n//2] * (n % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                a.append(0)\n",
    "            else:\n",
    "                a.append(a[-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * len(nums)\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            before = len(nums) - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        a = [0] * l\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                continue\n",
    "            else:\n",
    "                a[i] = (a[i-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * l\n",
    "        for i in range(l-2, -1, -1):\n",
    "            before = l - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(l):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if i == 0: \n",
    "                a.append(0)\n",
    "            else:\n",
    "                a.append(a[-1] + i * (n - nums[i-1]))\n",
    "\n",
    "        b = [0] * len(nums)\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            before = len(nums) - i - 1\n",
    "            n = nums[i]\n",
    "            b[i] = (b[i+1] + before * (nums[i+1] - n))\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(len(nums)):\n",
    "            ans = min(ans, a[i] + b[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        dp1 = [0]*n\n",
    "        dp2 = [0]*n\n",
    "\n",
    "        i = 0\n",
    "        cur = 0\n",
    "        while i < n-1:\n",
    "            while nums[i] == nums[i+1] and (i < n-1-1):\n",
    "                i += 1\n",
    "                dp1[i] = cur\n",
    "            change = (nums[i+1] - nums[i]) * (i+1)\n",
    "            cur += change\n",
    "            i+=1\n",
    "            dp1[i] = cur\n",
    "\n",
    "        i = n-1\n",
    "        cur = 0\n",
    "        while i > 0:\n",
    "            while nums[i] == nums[i-1] and (i > 0+1):\n",
    "                i -= 1\n",
    "                dp2[i] = cur\n",
    "            change = (nums[i] - nums[i-1]) * (n-i)\n",
    "            cur += change\n",
    "            i -= 1\n",
    "            dp2[i] = cur\n",
    "            \n",
    "        return(min([dp1[i]+dp2[i] for i in range(len(dp1))]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        k = (len(nums)+1)//2\n",
    "        left=[]\n",
    "        right=[]\n",
    "        \n",
    "        def quickselect(curnums,k)->int:\n",
    "            if len(curnums)==1:\n",
    "                return curnums[0]\n",
    "            nonlocal right\n",
    "            nonlocal left\n",
    "            pivot = random.sample(curnums,1)[0]\n",
    "            #print(pivot)\n",
    "            curleft=[]\n",
    "            curright=[]\n",
    "            curmid=[]\n",
    "            for x in curnums:\n",
    "                if x<pivot:\n",
    "                    curleft.append(x)\n",
    "                elif x==pivot:\n",
    "                    curmid.append(x)\n",
    "                else:\n",
    "                    curright.append(x)\n",
    "            r = len(curmid)+len(curleft)\n",
    "            print(k,len(curleft),r)\n",
    "            print(curleft,curmid, curright)\n",
    "            if len(curleft)>=k:\n",
    "                right+=curmid+curright\n",
    "                res = quickselect(curleft,k)\n",
    "            elif r<k:\n",
    "                left+=curmid+curleft\n",
    "                res = quickselect(curright,k-r)\n",
    "            else:\n",
    "                right+=curright\n",
    "                left+=curleft\n",
    "                res=pivot\n",
    "            \n",
    "            return res\n",
    "            \n",
    "        pivot = quickselect(nums,k)\n",
    "        print(pivot,left,right)\n",
    "        return pivot*(len(left))-sum(left)+sum(right)-pivot*(len(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if(n == 1):\n",
    "            return 0\n",
    "        elif(n == 2):\n",
    "            return abs(nums[0] - nums[1])\n",
    "        \n",
    "        temp = nums.copy()\n",
    "        temp.sort()\n",
    "\n",
    "        b1 = [0] * n\n",
    "        b2 = [0] * n\n",
    "        b = [0] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            b1[i] = b1[i-1] + (temp[i] - temp[i-1]) * i\n",
    "        for i in range(1, n):\n",
    "            b2[n-1-i] = b2[n-i] + (temp[n-i] - temp[n-1-i]) * i\n",
    "        \n",
    "        for i in range(n):\n",
    "            b[i] = b1[i] + b2[i]\n",
    "        \n",
    "        return min(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e, numbers):\n",
    "            idx = randint(s, e)\n",
    "            numbers[s], numbers[idx] = numbers[idx], numbers[s]\n",
    "\n",
    "            pivot = numbers[s]\n",
    "            l, r = s + 1, e\n",
    "\n",
    "            while l < r:\n",
    "                while numbers[l] <= pivot and l < r:\n",
    "                    l += 1\n",
    "                while numbers[r] > pivot and l < r:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    numbers[l], numbers[r] = numbers[r], numbers[l]\n",
    "                \n",
    "            if numbers[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            numbers[s], numbers[r] = numbers[r], numbers[s]\n",
    "\n",
    "            return r\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        def find_median(start, end, numbers, target_idx):\n",
    "            p_id = partition(start, end, numbers)\n",
    "\n",
    "            if p_id == target_idx:\n",
    "                return numbers[p_id]\n",
    "            elif p_id < target_idx:\n",
    "                return find_median(p_id + 1, end, numbers, target_idx)\n",
    "            else:\n",
    "                return find_median(start, p_id - 1, numbers, target_idx)\n",
    "\n",
    "        median = find_median(0, len(nums)-1, nums, len(nums)//2)\n",
    "        return sum(abs(n - median) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(nums, s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while nums[l] <= pivot and l < r:\n",
    "                    l += 1\n",
    "                while nums[r] >= pivot and l < r:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "            return r\n",
    "\n",
    "        def find_median(nums, s, e, target):\n",
    "            idx = partition(nums, s, e)\n",
    "\n",
    "            if idx < target:\n",
    "                return find_median(nums, idx+1, e, target)\n",
    "            elif idx > target:\n",
    "                return find_median(nums, s, idx-1, target)\n",
    "\n",
    "            return nums[idx]\n",
    "            \n",
    "\n",
    "        median = find_median(nums, 0, len(nums)-1, len(nums)//2)\n",
    "\n",
    "        return sum(abs(n-median) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while l < r and nums[l] <= pivot:\n",
    "                    l += 1\n",
    "                while l < r and nums[r] > pivot:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "\n",
    "            return r\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def find_median(start, end, target_idx):\n",
    "            idx = partition(start, end)\n",
    "\n",
    "            if idx < target_idx:\n",
    "                return find_median(idx+1, end, target_idx)\n",
    "            elif idx > target_idx:\n",
    "                return find_median(start,idx - 1, target_idx)\n",
    "\n",
    "            return nums[idx]\n",
    "        \n",
    "        median = find_median(0, len(nums)-1, len(nums) // 2)\n",
    "\n",
    "        return sum(abs(n - median) for n in nums)\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Quick Select: O(n+lgn),O(n)\n",
    "#median minimize l1 loss (sum of abs(y-x_i))\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def pivot(l,r):\n",
    "            p=nums[r]\n",
    "            j=l\n",
    "            for i in range(l,r):\n",
    "                if nums[i]<=p: #swap what's smaller to the front, maintaining a frontier j\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "                    j+=1\n",
    "            nums[r],nums[j]=nums[j],nums[r]\n",
    "            return j\n",
    "        \n",
    "        def randPivot(l,r):\n",
    "            i=random.randint(l,r)\n",
    "            nums[r],nums[i]=nums[i],nums[r]\n",
    "            return pivot(l,r)\n",
    "\n",
    "\n",
    "        def quickSelect(k,l,r): #find the kth smallest\n",
    "            if l>=r: return nums[l]\n",
    "            j=randPivot(l,r)\n",
    "            if j==k: return nums[k]\n",
    "            elif j>k: return quickSelect(k,l,j-1)\n",
    "            elif j<k: return quickSelect(k,j+1,r)\n",
    "\n",
    "        t=quickSelect(n//2,0,n-1)\n",
    "        return sum([abs(t-x) for x in nums])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        def partition(s, e):\n",
    "            p_id = randint(s, e)\n",
    "            pivot = nums[p_id]\n",
    "\n",
    "            nums[s], nums[p_id] = nums[p_id], nums[s]\n",
    "\n",
    "            l, r = s+1, e\n",
    "\n",
    "            while l < r:\n",
    "                while l < r and nums[l] <= pivot:\n",
    "                    l += 1\n",
    "                while l < r and nums[r] > pivot:\n",
    "                    r -= 1\n",
    "                \n",
    "                if l < r:\n",
    "                    nums[l], nums[r] = nums[r], nums[l]\n",
    "            \n",
    "\n",
    "            if nums[r] > pivot:\n",
    "                r -= 1\n",
    "            \n",
    "            nums[r], nums[s] = nums[s], nums[r]\n",
    "\n",
    "            return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def find_median(s, e, target_idx):\n",
    "            pivot_idx = partition(s, e)\n",
    "            \n",
    "            if pivot_idx < target_idx:\n",
    "                return find_median(pivot_idx + 1, e, target_idx)\n",
    "            elif pivot_idx > target_idx:\n",
    "                return find_median(s, pivot_idx - 1, target_idx)\n",
    "            \n",
    "            return nums[pivot_idx]\n",
    "\n",
    "        median = find_median(0, len(nums)-1, len(nums) // 2)\n",
    "\n",
    "        return sum(abs(median - n) for n in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minMoves2(self, nums: List[int]) -> int:\n",
    "        # # 找中位数\n",
    "        # nums.sort()\n",
    "        # return sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    def partition(self, nums, l, r):\n",
    "        i = random.randint(l, r)\n",
    "        nums[i], nums[r] = nums[r], nums[i]\n",
    "        pivt = nums[r]\n",
    "        i = l\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivt:#这里的到一定是小于等于的\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                i += 1\n",
    "        nums[i], nums[r] = nums[r], nums[i]\n",
    "        return i\n",
    "    #关键是快速选择的主程序是啥呢，这个是比较关键的\n",
    "    def quickselect(self, nums, l, r, k):\n",
    "        idx = self.partition(nums, l, r)\n",
    "        if idx == k:\n",
    "            return idx\n",
    "        if k < idx:\n",
    "            return self.quickselect(nums, l, idx - 1, k)\n",
    "        return self.quickselect(nums, idx+1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        helper = Helper()\n",
    "        idx = helper.quickselect(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            ans += abs(n - nums[idx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        x = self.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)\n",
    "\n",
    "    def randomPartition(self, nums, l, r):\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return self.partition(nums, l, r)\n",
    "\n",
    "    def partition(self, nums, l, r):\n",
    "        povit = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] < povit:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i+1],nums[r] = nums[r], nums[i+1]\n",
    "        return i + 1\n",
    "    \n",
    "    def quickSelected(self, nums, l, r, k):\n",
    "        index = self.randomPartition(nums, l, r)\n",
    "        if index == k:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return self.quickSelected(nums, l, index - 1, k )\n",
    "        return self.quickSelected(nums, index + 1, r, k)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def quick_select(nums, L, R, k):\n",
    "    \"\"\"快速选择, 返回 nums 中第 k 大的数 (k 从 0 开始).\"\"\"\n",
    "    t = randint(L, R)\n",
    "    nums[t], nums[R] = nums[R], nums[t]\n",
    "    left, idx = L - 1, L\n",
    "    while idx < R:\n",
    "        if nums[idx] > nums[R]:\n",
    "            left += 1\n",
    "            nums[left], nums[idx] = nums[idx], nums[left]\n",
    "        idx += 1\n",
    "    left += 1\n",
    "    nums[left], nums[R] = nums[R], nums[left]\n",
    "    if left == k:\n",
    "        return nums[left]\n",
    "    elif left > k:\n",
    "        return quick_select(nums, L, left - 1, k)\n",
    "    elif left < k:\n",
    "        return quick_select(nums, left + 1, R, k)\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mid = quick_select(nums,0,n-1,n//2)\n",
    "        ans = 0\n",
    "        for i ,v in enumerate(nums):\n",
    "            ans += abs(v-mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        def quick_sort(arr, l, r, k):\n",
    "            if l >= r: return arr[k]\n",
    "            i, j = l, r\n",
    "            random_index = random.randint(l, r)\n",
    "            arr[l], arr[random_index] = arr[random_index], arr[l]\n",
    "            pivot = arr[l]\n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= pivot: j -= 1\n",
    "                arr[i] = arr[j]\n",
    "                while i < j and arr[i] <= pivot: i += 1\n",
    "                arr[j] = arr[i]\n",
    "            arr[i] = pivot\n",
    "            if k < i: return quick_sort(arr, l, i - 1, k) \n",
    "            if k > i: return quick_sort(arr, i + 1, r, k)\n",
    "            return arr[k] #第k + 1小的数\n",
    "        n = len(nums)\n",
    "        mid = quick_sort(nums, 0, n - 1, n // 2)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans += abs(num - mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "\n",
    "        #每次增加或减少array中的一个元素\n",
    "        #最终所有的值全部都相同，相当于就是变成median啊\n",
    "        #O(N)内找到median\n",
    "        #有没有更好的方案？\n",
    "        #毕竟只需要返回一个数字，而不真的需要median\n",
    "        #每次只能修改一个元素\n",
    "        #一定是大家移动到median而不是大家一起抵达average。因为median两侧元素个数相同，这样相当于贪心地每次都是移动较少的元素\n",
    "        #修改partition算法，使得其可以在一次操作中就返回结果\n",
    "        #每次操作都是返回，将当前子序列修改到和第k个元素相同的成本\n",
    "        #在partition过程中，统计其移动的结果。其中数组和并不改变\n",
    "        #lessSum+largerSum+ (j-i)*pivot就是总的结果\n",
    "\n",
    "        def partition(nums,start,end,pivot):    #按照pivot执行\n",
    "            if start+1==end:\n",
    "                return 0,1,0,0      #严格小于，小于等于，小于的差值总和，大于的差值总和\n",
    "            i,j,k=start,start,end-1\n",
    "            lessSum=0\n",
    "            largerSum=0\n",
    "            while j<=k:\n",
    "                if nums[j]<pivot:\n",
    "                    lessSum+=pivot-nums[j]\n",
    "                    nums[i],nums[j]=nums[j],nums[i]\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                elif nums[j]>pivot:\n",
    "                    largerSum+=nums[j]-pivot\n",
    "                    nums[j],nums[k]=nums[k],nums[j]\n",
    "                    k-=1\n",
    "                else:\n",
    "                    j+=1\n",
    "            \n",
    "            return i-start,j-start,lessSum,largerSum      #小于，小于等于\n",
    "        \n",
    "        #将数组中所有的元素都变为第k大的元素的成本，返回值是第k个元素，以及变成其的成本。\n",
    "\n",
    "        def serachKth(nums,start,end,k):        #在start,end中搜索第k个元素。pivot可以取middle的\n",
    "            pivot=nums[start]\n",
    "            less,lessOrEqual,lessSum,largerSum=partition(nums,start,end,pivot)\n",
    "            #print(nums[start:end])\n",
    "            #print(less,lessOrEqual,lessSum,largerSum)\n",
    "            if k<=less:\n",
    "                #k比当前值小，则需要将所有的大值都变为pivot，然后将pivot\n",
    "                ans=largerSum      #全部更大的值都需要变为pivot\n",
    "                kthValue,cost=serachKth(nums,start,start+less,k)    #假设start:less已经全部变了\n",
    "                #将[start+less:end]的pivot值全部变为kthvalue\n",
    "                ans+=cost+(pivot-kthValue)*(end-start-less)\n",
    "                return kthValue,ans\n",
    "            elif less<k<=lessOrEqual:      \n",
    "                #第k个值就是pivot，则其成本是固定的\n",
    "                ans=lessSum+largerSum\n",
    "                return pivot,ans\n",
    "            else:   \n",
    "                #第k个值在大于的区间中\n",
    "                #\n",
    "                ans=lessSum\n",
    "                kthValue,cost=serachKth(nums,start+lessOrEqual,end,k-lessOrEqual)\n",
    "                ans+=cost+(kthValue-pivot)*lessOrEqual\n",
    "                return kthValue,ans\n",
    "        #注意kth是第k个\n",
    "        return serachKth(nums,0,len(nums),(len(nums)>>1)+1)[1]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "    def minMoves2(self, nums: List[int]) -> int:\r\n",
    "        def partition(nums, l, r):\r\n",
    "            pivot = nums[r]\r\n",
    "            i = l - 1\r\n",
    "            for j in range(l, r):\r\n",
    "                if nums[j] < pivot:\r\n",
    "                    i+=1\r\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\r\n",
    "            nums[i+1], nums[r] = nums[r], nums[i+1]\r\n",
    "            return i+1\r\n",
    "        \r\n",
    "    \r\n",
    "        def randomPartition(nums, l, r):\r\n",
    "            index = random.randint(l, r)\r\n",
    "            nums[r], nums[index] = nums[index], nums[r]\r\n",
    "            return partition(nums, l, r)\r\n",
    "        \r\n",
    "        def fastMid(nums, l, r, k):\r\n",
    "            index = randomPartition(nums, l, r)\r\n",
    "            if index == k:\r\n",
    "                return nums[k]\r\n",
    "            if index < k:\r\n",
    "                return fastMid(nums, index+1, r, k)\r\n",
    "            else:\r\n",
    "                return fastMid(nums, l, index-1, k)\r\n",
    "            \r\n",
    "        fast_mid = fastMid(nums, 0, len(nums) - 1, len(nums)//2)\r\n",
    "            \r\n",
    "        return sum(abs(num - fast_mid) for num in nums)\r\n",
    "    \r\n",
    "        # nums.sort()\r\n",
    "        # return sum(abs(num - nums[len(nums) // 2]) for num in nums)\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\r\n",
    "class Solution:\r\n",
    "    \r\n",
    "\r\n",
    "    \r\n",
    "    def minMoves2(self, nums: List[int]) -> int:\r\n",
    "        def partition(nums, l, r):\r\n",
    "            pivot = nums[r]\r\n",
    "            i = l - 1\r\n",
    "            for j in range(l, r):\r\n",
    "                if nums[j] < pivot:\r\n",
    "                    i+=1\r\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\r\n",
    "            nums[i+1], nums[r] = nums[r], nums[i+1]\r\n",
    "            return i+1\r\n",
    "        \r\n",
    "    \r\n",
    "        def randomPartition(nums, l, r):\r\n",
    "            index = random.randint(l, r)\r\n",
    "            nums[r], nums[index] = nums[index], nums[r]\r\n",
    "            return partition(nums, l, r)\r\n",
    "        \r\n",
    "        def fastMid(nums, l, r, k):\r\n",
    "            index = randomPartition(nums, l, r)\r\n",
    "            if index == k:\r\n",
    "                return nums[k]\r\n",
    "            if index < k:\r\n",
    "                return fastMid(nums, index+1, r, k)\r\n",
    "            else:\r\n",
    "                return fastMid(nums, l, index-1, k)\r\n",
    "            \r\n",
    "        fast_mid = fastMid(nums, 0, len(nums) - 1, len(nums)//2)\r\n",
    "        \r\n",
    "        result = 0\r\n",
    "        for item in nums:\r\n",
    "            result += abs(item - fast_mid)\r\n",
    "            \r\n",
    "            \r\n",
    "        return result\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        # 中位数贪心\n",
    "        # 快选找中位数\n",
    "        n = len(nums)\n",
    "        def partition(nums, l, r):\n",
    "            idx = randint(l, r)\n",
    "            nums[idx], nums[l] = nums[l], nums[idx]\n",
    "            pivot = nums[l]\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= pivot: \n",
    "                    r -= 1\n",
    "                nums[l] = nums[r]\n",
    "                while l < r and nums[l] < pivot: \n",
    "                    l += 1\n",
    "                nums[r] = nums[l]\n",
    "            nums[l] = pivot\n",
    "            return l\n",
    "        k = n // 2 + 1\n",
    "        def dfs(l, r):\n",
    "            p = partition(nums, l, r)\n",
    "            if p == k - 1:\n",
    "                return nums[p]\n",
    "            if p < k - 1:\n",
    "                return dfs(p+1, r)\n",
    "            return dfs(l, p-1)\n",
    "        \n",
    "        mid = dfs(0, n-1)\n",
    "        return sum(abs(mid - num) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Helper:\n",
    "    @staticmethod\n",
    "    def partition(nums: List[int], l: int, r: int) -> int:\n",
    "        pivot = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def randomPartition(nums: List[int], l: int, r: int) -> int:\n",
    "        i = randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return Helper.partition(nums, l, r)\n",
    "\n",
    "    @staticmethod\n",
    "    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:\n",
    "        index = Helper.randomPartition(nums, l, r)\n",
    "        if k == index:\n",
    "            return nums[k]\n",
    "        if k < index:\n",
    "            return Helper.quickSelected(nums, l, index - 1, k)\n",
    "        return Helper.quickSelected(nums, index + 1, r, k)\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        seed(time())\n",
    "        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)\n",
    "        return sum(abs(num - x) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves2(self, nums: List[int]) -> int:\n",
    "        # 中位数贪心\n",
    "        # 快选找中位数\n",
    "        n = len(nums)\n",
    "        def partition(nums, l, r):\n",
    "            print(l, r)\n",
    "            idx = randint(l, r)\n",
    "            nums[idx], nums[l] = nums[l], nums[idx]\n",
    "            pivot = nums[l]\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= pivot: \n",
    "                    r -= 1\n",
    "                nums[l] = nums[r]\n",
    "                while l < r and nums[l] < pivot: \n",
    "                    l += 1\n",
    "                nums[r] = nums[l]\n",
    "            nums[l] = pivot\n",
    "            return l\n",
    "        k = n // 2 + 1\n",
    "        def dfs(l, r):\n",
    "            p = partition(nums, l, r)\n",
    "            if p == k - 1:\n",
    "                return nums[p]\n",
    "            if p < k - 1:\n",
    "                return dfs(p+1, r)\n",
    "            return dfs(l, p-1)\n",
    "        \n",
    "        mid = dfs(0, n-1)\n",
    "        return sum(abs(mid - num) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        # 双指针\n",
    "        # 你大爷，不是双指针，我还抬举这道题了，直接减到0就完事了\n",
    "        # i = 0\n",
    "        j = len(nums) - 1\n",
    "        while j > 0:\n",
    "            diff = nums[j] - nums[0]\n",
    "            nums[j] -= diff\n",
    "            count += diff\n",
    "            # i += 1\n",
    "            j -= 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num= min(nums)\n",
    "        res = 0 \n",
    "        for num in nums:\n",
    "            res+=num-min_num \n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "      min_num = min(nums)\n",
    "      res = 0\n",
    "      for num in nums:\n",
    "          res += num - min_num\n",
    "      return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        minvalue=min(nums)\n",
    "        count=0\n",
    "        for i in nums:\n",
    "            count+=i-minvalue\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        # 这个算法太NB 了，聪明绝顶。\n",
    "        min_num = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num-min_num\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - min(nums) * len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        diff = nums[-1]-nums[0]\n",
    "        count = diff\n",
    "        while (diff != 0):\n",
    "            #print(diff)\n",
    "            tmp = nums.pop()\n",
    "            nums[-1] = count+nums[-1]\n",
    "            diff = nums[-1]-tmp\n",
    "            count += diff\n",
    "\n",
    "        return count \n",
    "        # 解题思路: 排序nums,计算diff = nums[-1]-nums[0],最小值到最大值的距离\n",
    "        # 然后保持nums[-1]不变,nums[0:n]增加diff,更新nums[0:n] count += diff\n",
    "        # 更新diff = nums[-2]-nums[-1],nums[0:n-1]增加diff,依次类推,count += diff\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        sum = 0 \n",
    "        min = nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            if(nums[i]<min):\n",
    "                min = nums[i]\n",
    "            sum += nums[i]\n",
    "        return sum-len(nums)*min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minMoves(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "\n",
    "#         if n == 1:\n",
    "#             return 0\n",
    "        \n",
    "#         t = 0\n",
    "#         for i in range(2*max(nums)):\n",
    "#             maxnum = max(nums)\n",
    "#             index = nums.index(maxnum)\n",
    "#             flag = 1\n",
    "#             if min(nums) != maxnum:\n",
    "#                 flag = 0\n",
    "#             nums[index] = min(nums)\n",
    "#             num2 = max(nums)\n",
    "#             dif = maxnum - num2    \n",
    "#             nums[index] = maxnum      \n",
    "#             nums[index] -= dif\n",
    "#             if flag == 1:\n",
    "#                 break\n",
    "#             t=t+dif\n",
    "#         return t\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - min_num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #n-1个元素加1相当于一个元素减1，所以最终求所有元素和最小元素差值\n",
    "        #只要求所有元素的和减去最小元素乘上n倍\n",
    "        return sum(nums)-len(nums)*min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - min_num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        minNum = min(nums)\n",
    "        moves = 0\n",
    "        for num in nums:\n",
    "            moves += num - minNum\n",
    "        return moves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums) if len(nums) !=1 else 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        nums_min = min(nums)\n",
    "        res = 0\n",
    "\n",
    "        for i in nums:\n",
    "            res += i - nums_min\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num  = min(nums)\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            count += num - min_num\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - min(nums) * len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        final = min(nums)\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            ans += (x - final)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums) if len(nums) != 1 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            result += num - min_num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        # (n-1)项+1 等价于 (1)项-1；所有项相等，即每一项降低到最小项\n",
    "        fmin = min(nums)\n",
    "        for i in nums:\n",
    "            res += i-fmin\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        cs=0\n",
    "        for num in nums:\n",
    "            cs += num-min_num\n",
    "        return cs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        m = min(nums)\n",
    "        for i in nums:\n",
    "            count += i-m\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums)-min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #n-1个元素加1相当于一个元素减1，所以最终求所有元素和最小元素差值\n",
    "        #只要求所有元素的和减去最小元素乘上n倍\n",
    "        lens,sums = len(nums),0\n",
    "        mins = nums[0]\n",
    "        for i in nums:\n",
    "            #lens += 1\n",
    "            sums += i\n",
    "            if i < mins:\n",
    "                mins = i\n",
    "        return sums - mins*lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #让n-1个元素加1，与最大的元素减1效果一样，差值变化一样\n",
    "        #相对运动\n",
    "        #因此可以转化为每次让一个元素减1，求所有元素相等的最少操作次数\n",
    "        '''\n",
    "        minval=float('inf')\n",
    "        for num in nums：\n",
    "           minval=min(minval,num)\n",
    "        res=0 #统计减少次数\n",
    "        for num in nums:\n",
    "            res+=num-minval#每一个非最小值减去最小值得到变化次数\n",
    "        return res\n",
    "        '''\n",
    "        #数学方法\n",
    "        #假设最少的操作次数为k，k次操作后每个元素相等，假设相等元素为target\n",
    "        #因此n-1个元素要进行+1操作，增加次数k(n-1)\n",
    "        #原本列表和sum（nums）,k次操作后k(n-1)+sum(nums)=n(target)\n",
    "        if len(nums)!=1:\n",
    "            return sum(nums)-len(nums)*min(nums)\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        return sum(nums)-len(nums)*min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num=min(nums)\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            res+=num-min_num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #n-1个元素加1相当于一个元素减1，所以最终求所有元素和最小元素差值\n",
    "        #只要求所有元素的和减去最小元素乘上n倍\n",
    "        lens,sums = 0,0\n",
    "        mins = nums[0]\n",
    "        for i in nums:\n",
    "            lens += 1\n",
    "            sums += i\n",
    "            if i < mins:\n",
    "                mins = i\n",
    "        return sums - mins*lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        miln = sum(nums) - min(nums)*len(nums)\n",
    "        return miln\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_nums = min(nums)\n",
    "        min_moves = 0\n",
    "        for i in nums:\n",
    "            min_moves  = (i - min_nums) + min_moves\n",
    "        \n",
    "        return min_moves\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        for n in nums:\n",
    "            ans+=n-nums[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        sum1=0\n",
    "        for i in range(0,len(nums)-1):\n",
    "            diff=nums[i+1]-nums[i]\n",
    "            count=diff*(len(nums)-i-1)\n",
    "            sum1+=count\n",
    "        \n",
    "        #nums.pop(-1)\n",
    "\n",
    "\n",
    "        return(sum1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_mum = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num-min_mum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - min_num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min = nums[0]\n",
    "        for num in nums:\n",
    "            if num < min:\n",
    "                min = num\n",
    "                \n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num-min\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minMoves(self, nums):\n",
    "        return sum(nums) - len(nums)*min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        # 一个元素减1\n",
    "        a,ans=min(nums),0\n",
    "        for i in nums:\n",
    "            ans+=i-a\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #n-1个元素加1相当于一个元素减1，所以最终求所有元素和最小元素差值\n",
    "        #只要求所有元素的和减去最小元素乘上n倍\n",
    "        lens,sums = 0,0\n",
    "        mins = nums[0]\n",
    "        for i in nums:\n",
    "            lens += 1\n",
    "            sums += i\n",
    "            if i < mins:\n",
    "                mins = i\n",
    "        return sums - mins*lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums)-len(nums)*min(nums) if len(nums) !=1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minMoves(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        sum_val = sum(nums)\r\n",
    "        min_val = min(nums)\r\n",
    "        return(sum_val - min_val * n)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minMoves(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        sum_val = sum(nums)\r\n",
    "        min_val = min(nums)\r\n",
    "        return(sum_val - min_val * n)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums)-min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - min(nums) * len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        #n-1个元素加1相当于一个元素减1，所以最终求所有元素和最小元素差值\n",
    "        #只要求所有元素的和减去最小元素乘上n倍\n",
    "        lens,sums = len(nums),0\n",
    "        mins = nums[0]\n",
    "        for i in nums:\n",
    "            #lens += 1\n",
    "            sums += i\n",
    "            if i < mins:\n",
    "                mins = i\n",
    "        return sums - mins*lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        minvalue=min(nums)\n",
    "        time=0\n",
    "        for i in nums:\n",
    "            time+=i-minvalue\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "\n",
    "        return sum(nums)-len(nums)*min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        mintarget=min(nums)\n",
    "        res=0\n",
    "        for i in range(len(nums)):\n",
    "            res+=nums[i]-mintarget\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - (min(nums) * len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minMoves(self, nums):\n",
    "        res = sum(nums) - len(nums)*min(nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        # flag = 0\n",
    "        # if len(nums) == 2 and nums[0] != nums[1]:\n",
    "        #     return abs(nums[0] - nums[1])\n",
    "        # while len(set(nums)) != 1:\n",
    "        #     nums.sort()\n",
    "        #     for i in range(len(nums)-1):\n",
    "        #         nums[i] += 1\n",
    "        #     flag += 1\n",
    "        # return flag\n",
    "\n",
    "        # n-1块加1，等于1块减1\n",
    "        return sum(nums) - min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        minNum=min(nums)\n",
    "        res=0\n",
    "        for num in nums:\n",
    "            res+=num-minNum\n",
    "        return res;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums) if len(nums) != 1 else 0\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - min_num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        min_ = min(nums)\n",
    "        for num in nums:\n",
    "            res += num -min_\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        mins = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - mins\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        num_min = min(nums)\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            res += nums[i] - num_min\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        minNum = min(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res += num - minNum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - len(nums) * min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums)-len(nums)*min(nums) if len(nums) != 1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums)-min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        mintarget=min(nums)\n",
    "        res=0\n",
    "        for i in range(len(nums)):\n",
    "            res+=nums[i]-mintarget\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        \n",
    "        min_val = min(nums)\n",
    "\n",
    "        ans = 0 \n",
    "        for x in nums:\n",
    "            ans += x-min_val\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minMoves(self, nums):\n",
    "        sum = 0\n",
    "        minmum = min(nums)\n",
    "        for i in nums:\n",
    "            sum += i-minmum\n",
    "        return sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        # 理解： n-1元素加一，相当于一个元素每次减1\n",
    "        # 减到最后所有元素都为数组中最小的值\n",
    "        return sum(nums)-min(nums)*len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        m = min(nums)\n",
    "        return sum([n - m for n in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        return sum(nums) - min(nums) * len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        mn = min(nums)\n",
    "        return sum(x - mn for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        min_num = min(nums)\n",
    "        return sum([num - min_num for num in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int]) -> int:\n",
    "        sum = 0\n",
    "        minmum = min(nums)\n",
    "        for i in nums:\n",
    "            sum += i-minmum\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "\n",
    "        #差分统计 以目标和为主线\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        sum_diff = [0 for _ in range(2 * limit + 2)]    #targetSum_operation\n",
    "\n",
    "        for i in range(n // 2):\n",
    "\n",
    "            A, B = nums[i], nums[n-1-i]\n",
    "\n",
    "\n",
    "\n",
    "            L = 2\n",
    "\n",
    "            R = 2 * limit\n",
    "\n",
    "            sum_diff[L]     += 2\n",
    "\n",
    "            sum_diff[R + 1] -= 2\n",
    "\n",
    "            ####操作多了的情况，这个情况1步就ok\n",
    "\n",
    "            L = min(A,B) + 1\n",
    "\n",
    "            R = max(A,B) + limit\n",
    "\n",
    "            sum_diff[L]     -= 1\n",
    "\n",
    "            sum_diff[R + 1] += 1\n",
    "\n",
    "            ####操作多了的情况，这个情况0步就ok\n",
    "\n",
    "            L = A + B\n",
    "\n",
    "            R = A + B\n",
    "\n",
    "            sum_diff[L]     -= 1\n",
    "\n",
    "            sum_diff[R + 1] += 1\n",
    "\n",
    "\n",
    "\n",
    "        res = n     #最多的情况，是每个数字都要操作\n",
    "\n",
    "        cur_op = 0\n",
    "\n",
    "        for ab_sum in range(2, 2*limit+1):\n",
    "\n",
    "            cur_op += sum_diff[ab_sum]\n",
    "\n",
    "            res = min(res, cur_op)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        for i in range(len(nums)//2):\n",
    "            left = min(nums[i], nums[len(nums) - 1 - i]) + 1\n",
    "            right = max(nums[i], nums[len(nums) - 1 - i]) + limit\n",
    "            diff[2] += 2\n",
    "            diff[left] -= 1\n",
    "            diff[nums[i] + nums[len(nums) - 1 - i]] -= 1\n",
    "            diff[nums[i] + nums[len(nums) - 1 - i] + 1] += 1\n",
    "            diff[right + 1] += 1\n",
    "        ans = inf\n",
    "        temp = 0\n",
    "        for i in range(2, len(diff)):\n",
    "            temp += diff[i]\n",
    "            ans = min(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        delta = [0] * (limit * 2 + 2)\n",
    "        for i in range(int(n / 2)):\n",
    "            lo = 1 + min(nums[i], nums[n - i - 1])\n",
    "            hi = limit + max(nums[i], nums[n - i - 1])\n",
    "            sum = nums[i] + nums[n - i - 1]\n",
    "            delta[lo] -= 1\n",
    "            delta[sum] -= 1\n",
    "            delta[sum + 1] += 1\n",
    "            delta[hi + 1] += 1\n",
    "        now = ans = n \n",
    "        for i in range(limit * 2 + 1):\n",
    "            now += delta[i]\n",
    "            ans = min(ans, now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/\n",
    "    # 使得数组互补的最少操作次数\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        # 查分数组 求前缀和就是数字为i时候需要操作的最少次数\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        n = len(nums)\n",
    "        for i in range(n >> 1):\n",
    "            # 这一个pair导致只要在low和hi之间的数字都可以少操作一次\n",
    "            # 同时sm可以少操作两次\n",
    "            low, hi = 1 + min(nums[i], nums[n - i - 1]), limit + max(nums[i], nums[n - i - 1])\n",
    "            sm = nums[i] + nums[n - i - 1]\n",
    "            diff[low] -= 1\n",
    "            diff[hi + 1] += 1\n",
    "            diff[sm] -= 1\n",
    "            diff[sm + 1] += 1\n",
    "        ans = now = n\n",
    "        for i in diff:\n",
    "            now += i\n",
    "            ans = ans if ans < now else now\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        for i in range(n//2):\n",
    "            num1 = nums[i]\n",
    "            num2 = nums[n-1-i]\n",
    "            l = 2\n",
    "            r = 2*limit\n",
    "            diff[l] += 2\n",
    "            diff[r+1] -= 2\n",
    "            l = 1+min(num1,num2)\n",
    "            r = limit + max(num1,num2)\n",
    "            diff[l] += -1\n",
    "            diff[r+1] -=-1\n",
    "            l = r = num1 + num2\n",
    "            diff[l] += -1\n",
    "            diff[r+1] -= -1\n",
    "        ans = n\n",
    "        sum_ = 0\n",
    "        for i in range(2,2*limit+1):\n",
    "            sum_ += diff[i]\n",
    "            ans = min(ans,sum_)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        #差分统计 以目标和为主线\n",
    "        n = len(nums)\n",
    "        sum_diff = [0 for _ in range(2 * limit + 2)]    #targetSum_operation\n",
    "        for i in range(n // 2):\n",
    "            A, B = nums[i], nums[n-1-i]\n",
    "\n",
    "            L = 2\n",
    "            R = 2 * limit\n",
    "            sum_diff[L]     += 2\n",
    "            sum_diff[R + 1] -= 2\n",
    "            ####操作多了的情况，这个情况1步就ok\n",
    "            L = min(A,B) + 1\n",
    "            R = max(A,B) + limit\n",
    "            sum_diff[L]     -= 1\n",
    "            sum_diff[R + 1] += 1\n",
    "            ####操作多了的情况，这个情况0步就ok\n",
    "            L = A + B\n",
    "            R = A + B\n",
    "            sum_diff[L]     -= 1\n",
    "            sum_diff[R + 1] += 1\n",
    "\n",
    "        res = n     #最多的情况，是每个数字都要操作\n",
    "        cur_op = 0\n",
    "        for ab_sum in range(2, 2*limit+1):\n",
    "            cur_op += sum_diff[ab_sum]\n",
    "            res = min(res, cur_op)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        #差分统计 以目标和为主线\n",
    "        n = len(nums)\n",
    "        sum_diff = [0 for _ in range(2 * limit + 2)]    #targetSum_operation\n",
    "        for i in range(n // 2):\n",
    "            A, B = nums[i], nums[n-1-i]\n",
    "\n",
    "            L = 2\n",
    "            R = 2 * limit\n",
    "            sum_diff[L]     += 2\n",
    "            sum_diff[R + 1] -= 2\n",
    "            ####操作多了的情况，这个情况1步就ok\n",
    "            L = min(A,B) + 1\n",
    "            R = max(A,B) + limit\n",
    "            sum_diff[L]     -= 1\n",
    "            sum_diff[R + 1] += 1\n",
    "            ####操作多了的情况，这个情况0步就ok\n",
    "            L = A + B\n",
    "            R = A + B\n",
    "            sum_diff[L]     -= 1\n",
    "            sum_diff[R + 1] += 1\n",
    "\n",
    "        res = n     #最多的情况，是每个数字都要操作\n",
    "        cur_op = 0\n",
    "        for ab_sum in range(2, 2*limit+1):\n",
    "            cur_op += sum_diff[ab_sum]\n",
    "            res = min(res, cur_op)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0 for i in range(2*limit + 2)]\n",
    "\n",
    "        for i in range(n//2):\n",
    "            a = min(nums[i], nums[n-1-i])\n",
    "            b = max(nums[i], nums[n-1-i])\n",
    "            diff[2] += 2\n",
    "            diff[a+1] -= 2\n",
    "            diff[a+1] += 1\n",
    "            diff[a+b] -= 1\n",
    "            diff[a+b+1] += 1\n",
    "            diff[b+limit+1] -= 1\n",
    "            diff[b+limit+1] += 2\n",
    "            \n",
    "        \n",
    "        ans = n\n",
    "        total = diff[1]\n",
    "        for i in range(2,2*limit+2):\n",
    "            total = total + diff[i]\n",
    "            ans = min(ans, total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "\n",
    "        # n = len(nums)\n",
    "        # pairs = (n + 1) // 2\n",
    "\n",
    "        # d = defaultdict(int)\n",
    "        # for l in range(pairs):\n",
    "        #     r = n - 1 - l\n",
    "        #     d[nums[l] + nums[r]] += 1\n",
    "        #     if nums[l] > nums[r]:\n",
    "        #         nums[l], nums[r] = nums[r], nums[l]\n",
    "        \n",
    "\n",
    "        # cans = list([(v, k) for k,v in d.items()])\n",
    "        # cans.sort(reverse = True)\n",
    "\n",
    "        # #print(pairs)\n",
    "        # #print(cans)\n",
    "        # #print(nums)\n",
    "\n",
    "        # # return\n",
    "\n",
    "        # # a special case sum = limit + 1, which insure a all pair could achieve by only 1 operation, so min_op should be pairs\n",
    "        # min_op = pairs\n",
    "        # min_extra = 0\n",
    "        # for v, k in cans:\n",
    "\n",
    "        #     cur_op = 0\n",
    "        #     cur_extra = 0\n",
    "\n",
    "        #     #print(f'pairs: {pairs}, v: {v}, min_op: {min_op}, min_extra: {min_extra}')\n",
    "        #     # (pairs - v) is the minimum op number need, min_op - (pairs - v) is the maximum extra number allowed\n",
    "        #     max_extra = min_op - (pairs - v)\n",
    "        #     if max_extra <= 0:\n",
    "        #         # print('here')\n",
    "        #         break\n",
    "            \n",
    "             \n",
    "\n",
    "        #     for l in range(pairs):\n",
    "        #         r = n - 1 - l\n",
    "        #         cv = nums[l] + nums[r] \n",
    "        #         if cv > k:\n",
    "        #             if nums[r] - 1 < cv - k:\n",
    "\n",
    "        #                 #print(f'{cv}')\n",
    "        #                 cur_op += 2\n",
    "        #                 cur_extra += 1\n",
    "        #             else:\n",
    "        #                 cur_op += 1\n",
    "        #         elif cv < k:\n",
    "\n",
    "        #             #print(f'{limit - nums[l]} {cv - k}')\n",
    "        #             if limit - nums[l] < k - cv:\n",
    "        #                 #print(f'xx {cv}')\n",
    "        #                 cur_op += 2\n",
    "        #                 cur_extra += 1\n",
    "        #             else:\n",
    "        #                 cur_op += 1\n",
    "                \n",
    "        #         if cur_extra == max_extra:\n",
    "        #             break\n",
    "            \n",
    "        #     if cur_extra == max_extra:\n",
    "        #         continue\n",
    "            \n",
    "        #     #print(f'cur_op: {cur_op}, cur_extra: {cur_extra}, min_op: {min_op}, min_extra: {min_extra}')\n",
    "        #     if cur_op <= min_op:\n",
    "        #         min_op = cur_op\n",
    "        #         min_extra = cur_extra\n",
    "\n",
    "        # return min_op\n",
    "\n",
    "        n = len(nums)\n",
    "        pairs = n // 2\n",
    "        arr = [0] * (limit * 2 + 2)\n",
    "        for l in range(pairs):\n",
    "            # r = n - 1 - l\n",
    "\n",
    "            # sum_v = nums[l] + nums[r]\n",
    "\n",
    "            a = nums[l]\n",
    "            b = nums[n - 1 - l]\n",
    "\n",
    "            arr[2] += 2\n",
    "            arr[1 + min(a, b)] -= 1\n",
    "            arr[a + b] -= 1\n",
    "            arr[a + b + 1] += 1\n",
    "            arr[limit + max(a, b) + 1] += 1\n",
    "\n",
    "            # if sum_v == 2:\n",
    "            #     arr[sum_v + 1] += 1\n",
    "            #     arr[first_op_max + 1] += 1\n",
    "            # elif sum_v == limit * 2:\n",
    "            #     arr[2] += 2\n",
    "            #     arr[first_op_min] -= 1\n",
    "            #     arr[sum_v] -= 1\n",
    "            # else:\n",
    "            #     arr[2] += 2\n",
    "            #     arr[first_op_min] -= 1\n",
    "            #     arr[sum_v] -= 1\n",
    "            #     arr[sum_v + 1] += 1\n",
    "            #     arr[first_op_max + 1] += 1\n",
    "        \n",
    "        #print(arr)\n",
    "\n",
    "        ret = inf\n",
    "        cur = 0\n",
    "        for i in range(2, limit * 2 + 1):\n",
    "            cur += arr[i]\n",
    "            ret = min(ret, cur)\n",
    "        \n",
    "        #print(d)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        d = [0] * (2 * limit + 2)\n",
    "\n",
    "        i, j = 0, len(nums) - 1\n",
    "        while i < j:\n",
    "            l, r = 2, 2 * limit\n",
    "            d[l] += 2\n",
    "            d[r + 1] -= 2\n",
    "\n",
    "            l = 1 + min(nums[i], nums[j])\n",
    "            r = limit + max(nums[i], nums[j])\n",
    "            d[l] += -1\n",
    "            d[r + 1] -= -1\n",
    "\n",
    "            d[nums[i] + nums[j]] += -1 \n",
    "            d[nums[i] + nums[j] + 1] -= -1 \n",
    "        \n",
    "            i += 1\n",
    "            j -= 1\n",
    "        res = inf\n",
    "        s = 0\n",
    "        for i in range(2, 2 * limit + 1, 1):\n",
    "            s += d[i]\n",
    "            res = min(res, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def minMoves(self, nums:list[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        List = [0]*(2*limit+2) #创建差分数组，初始操作数差值为0，索引代表互补目标数，List[2*limit+1]作为[2,2*limit]的右差分参考值\n",
    "        for i in range(n//2):\n",
    "            l,r = nums[i],nums[n-1-i]\n",
    "            left = 2 #最小和为2\n",
    "            right = 2*limit+1 #最大和为2limit，故右差分索引为2*limit+1\n",
    "            #对于任意i有nums[i]+nums[n-1-i]属于区间[2,2*limit]，最多需要操作两次，令区间[2,2*limit]的操作次数初始化为2,故差分数组做如下修改:\n",
    "            List[left] += 2 \n",
    "            List[right] -= 2\n",
    "            #又因为对任意i有nums[i]+nums[n-1-i]属于区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]的操作次数仅需1次，令区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]的操作数减少1，故对差分数组做如下修改:\n",
    "            left = min(nums[i],nums[n-i-1]) + 1\n",
    "            right = max(nums[i],nums[n-i-1]) + limit+1\n",
    "            List[left] -= 1 \n",
    "            List[right] += 1\n",
    "            #当nums[i]+nums[n-1-i]等于目标值时，此时不用修改任何操作数，所以令nums[i]+nums[n-1-i]的操作数为0，且nums[i]+nums[n-1-i]属于区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]，故对差分数组再减1即可:\n",
    "            left = nums[i]+nums[n-1-i]\n",
    "            right = nums[i]+nums[n-1-i] + 1\n",
    "            List[left] -= 1 \n",
    "            List[right] += 1\n",
    "        #考虑极端情况，所有的数都需要修改，故最大操作数为n\n",
    "        ans = n\n",
    "        #初始操作数为0\n",
    "        op = 0 \n",
    "\n",
    "\n",
    "        #已知差分数组d，可得原数组a[n] = sum(d[0:n])\n",
    "        for dsum in List[2:-1]:\n",
    "            op += dsum\n",
    "            ans = min(op,ans)\n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        # 互补 哈希表前缀和套路题\n",
    "        n = len(nums)\n",
    "        # 差分数组 的前缀和\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        for i in range(n >> 1):\n",
    "            # 正难则反 这个区间段之内的数字可以少操作一次\n",
    "            # sm这个点可以少操作两次\n",
    "            low, high = 1 + min(nums[i], nums[n-i-1]), limit + max(nums[i], nums[n-i-1])\n",
    "            sm = nums[i] + nums[n-i-1]\n",
    "            diff[low] -= 1\n",
    "            diff[sm] -= 1\n",
    "            diff[sm + 1] += 1\n",
    "            diff[high + 1] += 1\n",
    "        now = ans = len(nums)\n",
    "        for i in diff:\n",
    "            now += i\n",
    "            ans = min(ans, now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        List = [0]*(2*limit+2) #创建差分数组，初始操作数差值为0，索引代表互补目标数，List[2*limit+1]作为[2,2*limit]的右差分参考值\n",
    "        for i in range(n//2):\n",
    "            l,r = nums[i],nums[n-1-i]\n",
    "            left = 2   #最小和为2\n",
    "            right = 2*limit+1   #最大和为2limit，故右差分索引为\n",
    "            #对于任意i有nums[i]+nums[n-1-i]属于区间[2,2*limit]，最多需要操作两次，令区间[2,2*limit]的操作次数初始化为2,故差分数组做如下修改:\n",
    "            List[left] += 2 \n",
    "            List[right] -= 2\n",
    "            #又因为对任意i有nums[i]+nums[n-1-i]属于区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]的操作次数仅需1次，令区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]的操作数减少1，故对差分数组做如下修改:\n",
    "            left = min(nums[i],nums[n-i-1]) + 1\n",
    "            right = max(nums[i],nums[n-i-1]) + limit+1\n",
    "            List[left] -= 1 \n",
    "            List[right] += 1\n",
    "            #当nums[i]+nums[n-1-i]等于目标值时，此时不用修改任何操作数，所以令nums[i]+nums[n-1-i]的操作数为0，且nums[i]+nums[n-1-i]属于区间[min(nums[i],nums[n-i-1])+1,max(nums[i],nums[n-i-1])+limit]，故对差分数组再减1即可:\n",
    "            left = nums[i]+nums[n-1-i]\n",
    "            right = nums[i]+nums[n-1-i] + 1\n",
    "            List[left] -= 1 \n",
    "            List[right] += 1\n",
    "        #考虑极端情况，所有的数都需要修改，故最大操作数为n\n",
    "        ans = n\n",
    "        #初始操作数为0\n",
    "        op = 0 \n",
    "\n",
    "        #已知差分数组d，可得原数组a[n] = sum(d[0:n])\n",
    "        for dsum in List[2:-1]:\n",
    "            op += dsum\n",
    "            ans = min(op,ans)\n",
    "        return ans           \n",
    "\n",
    "        # n = len(nums)\n",
    "        # List = [0]*(2*limit+1)      \n",
    "        # for targe in range(2,2*limit+1):\n",
    "        #     for i in range(n//2):\n",
    "        #         if nums[i]+nums[n-i-1]==targe:\n",
    "        #             List[targe] = List[targe]\n",
    "        #             continue\n",
    "        #         if nums[i]+nums[n-i-1] < targe:\n",
    "        #             if max(nums[i]+limit,nums[n-i-1]+limit) >= targe:\n",
    "        #                 List[targe] += 1\n",
    "        #             else:\n",
    "        #                 List[targe] += 2\n",
    "        #         else:\n",
    "        #             if min(nums[i]+1,1+nums[n-i-1]) <= targe :\n",
    "        #                 List[targe] += 1 \n",
    "        #             else:\n",
    "        #                 List[targe] += 2\n",
    "\n",
    "        return min(List[2:])\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "     \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0 for i in range(2*limit+2)]\n",
    "        for i in range(n//2):\n",
    "            a = min(nums[i], nums[n-1-i]) + 1\n",
    "            ab = nums[i] + nums[n-1-i]\n",
    "            bl = max(nums[i], nums[n-1-i]) + limit\n",
    "            diff[a] -= 1\n",
    "            diff[ab] -= 1\n",
    "            diff[ab+1] += 1\n",
    "            diff[bl + 1] += 1\n",
    "        total = n\n",
    "        ans = n\n",
    "        d = len(diff)\n",
    "        for i in range(2,2*limit+2):\n",
    "            total = total + diff[i]\n",
    "            ans = min(total, ans) \n",
    "        print(diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 2023-09-22 13:46:29\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        for x, y in zip(nums[: n >> 1], nums[::-1][: n >> 1]):\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "\n",
    "            diff[1 + x] -= 1\n",
    "            diff[x + y] -= 1\n",
    "            diff[x + y + 1] += 1\n",
    "            diff[y + limit + 1] += 1\n",
    "\n",
    "        res = cur = n\n",
    "\n",
    "        for d in diff:\n",
    "            cur += d\n",
    "            res = min(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 差分数组 d，范围是 [1, 2*limit+1]\n",
    "        d = [0] * (limit * 2 + 2)\n",
    "        # 记录 nums[i] + nums[n-i-1] 的频数\n",
    "        freq = collections.Counter()\n",
    "        for i in range(n // 2):\n",
    "            freq[nums[i] + nums[n - i - 1]] += 1\n",
    "            # 对差分数组进行操作\n",
    "            d[1 + min(nums[i], nums[n - i - 1])] += 1\n",
    "            d[limit + max(nums[i], nums[n - i - 1]) + 1] -= 1\n",
    "        \n",
    "        ans = n * 2\n",
    "        # 0/1 贡献的数量\n",
    "        contrib01 = 0\n",
    "        for K in range(2, limit * 2 + 1):\n",
    "            contrib01 += d[K]\n",
    "            # 通过哈希表查找 0 贡献的数量\n",
    "            contrib0 = freq[K]\n",
    "            contrib1 = contrib01 - contrib0\n",
    "            contrib2 = n // 2 - contrib01\n",
    "            ans = min(ans, contrib1 + contrib2 * 2)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l < r:\n",
    "            a = nums[l]\n",
    "            b = nums[r]\n",
    "            diff[2] += 2\n",
    "            diff[2 * limit + 1] -= 2\n",
    "            diff[min(a, b) + 1] -= 1\n",
    "            diff[max(a, b) + limit + 1] += 1\n",
    "            diff[a + b] -= 1\n",
    "            diff[a + b + 1] += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return min(accumulate(diff[2:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        d = [0] * (limit*2+2)         # 范围 [1, 2*limit+1]\n",
    "        freq = collections.Counter()  # 记录 nums[i] + nums[n-i-1] 的频数\n",
    "        for i in range(n//2):\n",
    "            freq[nums[i] + nums[n-i-1]] += 1\n",
    "            # 对差分数组进行操作\n",
    "            d[1 + min(nums[i], nums[n-i-1])] += 1\n",
    "            d[limit + max(nums[i], nums[n-i-1]) + 1] -= 1\n",
    "        \n",
    "        ans = n * 2\n",
    "        contrib01 = 0  # 0贡献的数量\n",
    "        for K in range(2, limit*2+1):\n",
    "            contrib01 += d[K]               # 0和1 贡献的数量\n",
    "            contrib1 = contrib01 - freq[K]  # 1 贡献的数量\n",
    "            contrib2 = n // 2 - contrib01   # 剩下的都是 2 贡献的数量\n",
    "            ans = min(ans, contrib1+contrib2*2)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        maxl = 200002\n",
    "        arr = [0] * maxl\n",
    "        \n",
    "        for i in range(n // 2):\n",
    "            num1 = nums[i]\n",
    "            num2 = nums[n - i - 1]\n",
    "            num1, num2 = min(num1, num2), max(num1, num2)\n",
    "\n",
    "            arr[num1 + 1] += 1\n",
    "            arr[num1 + num2] -= 1\n",
    "\n",
    "            arr[num1 + num2 + 1] += 1\n",
    "            arr[num2 + limit + 1] -= 1\n",
    "\n",
    "            arr[2] += 2\n",
    "            arr[num1 + 1] -= 2\n",
    "\n",
    "            arr[limit + num2 + 1] += 2\n",
    "            arr[limit * 2 + 1] -= 2\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(2, 2 * limit + 1):\n",
    "            arr[i] += arr[i - 1]\n",
    "            ans = min(ans, arr[i])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        d = [0] * (limit * 2 + 2)\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n >> 1):\n",
    "            a, b = min(nums[i], nums[n - i - 1]), max(nums[i], nums[n - i - 1])\n",
    "            d[2] += 2\n",
    "            d[limit * 2 + 1] -= 2\n",
    "\n",
    "            d[a + 1] -= 1\n",
    "            d[b + limit + 1] += 1\n",
    "\n",
    "            d[a + b] -= 1\n",
    "            d[a + b + 1] += 1\n",
    "\n",
    "        result, s = n, 0\n",
    "        for v in d[2: limit * 2 + 1]:\n",
    "            s += v\n",
    "            if result > s:\n",
    "                result = s\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l < r:\n",
    "            a = nums[l]\n",
    "            b = nums[r]\n",
    "            diff[2] += 2\n",
    "            diff[2 * limit + 1] -= 2\n",
    "            diff[min(a, b) + 1] -= 1\n",
    "            diff[max(a, b) + limit + 1] += 1\n",
    "            diff[a + b] -= 1\n",
    "            diff[a + b + 1] += 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return min(accumulate(diff[2:-1]))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        maxl = 200005\n",
    "        arr = [0] * maxl\n",
    "        \n",
    "        for i in range(n // 2):\n",
    "            num1 = nums[i]\n",
    "            num2 = nums[n - i - 1]\n",
    "            num1, num2 = min(num1, num2), max(num1, num2)\n",
    "\n",
    "            arr[num1 + 1] += 1\n",
    "            arr[num1 + num2] -= 1\n",
    "\n",
    "            arr[num1 + num2 + 1] += 1\n",
    "            arr[num2 + limit + 1] -= 1\n",
    "\n",
    "            arr[2] += 2\n",
    "            arr[num1 + 1] -= 2\n",
    "\n",
    "            arr[limit + num2 + 1] += 2\n",
    "            arr[limit * 2 + 1] -= 2\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(2, 2 * limit + 1):\n",
    "            arr[i] += arr[i - 1]\n",
    "            ans = min(ans, arr[i])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        #差分数组\n",
    "        n=len(nums)\n",
    "        s=[0 for i in range(2*limit+2)]\n",
    "        for i in range(n//2):\n",
    "            if nums[i]<nums[n-1-i]:\n",
    "                x=nums[i]\n",
    "                y=nums[n-1-i]\n",
    "            else:\n",
    "                x=nums[n-1-i]\n",
    "                y=nums[i]\n",
    "            s[2]+=2\n",
    "            s[x+1]-=1\n",
    "            s[x+y]-=1\n",
    "            s[x+y+1]+=1\n",
    "            s[y+limit+1]+=1\n",
    "        ans=s[2]\n",
    "        x=0\n",
    "        for i in range(2,2*limit+2):\n",
    "            s[i]=s[i]+x\n",
    "            x=s[i]\n",
    "            ans=min(ans,x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        min_move = [0] * (limit * 2 + 2)\n",
    "\n",
    "        for i in range(n // 2):\n",
    "            a, b = nums[i], nums[n - 1 - i]\n",
    "\n",
    "            min_move[2] += 2\n",
    "            min_move[2 * limit + 1] -= 2\n",
    "\n",
    "            min_move[1 + min(a,b)] -= 1\n",
    "            min_move[limit + max(a,b) + 1] += 1\n",
    "\n",
    "            min_move[a + b] -= 1\n",
    "            min_move[a + b + 1] += 1\n",
    "\n",
    "        ans = n\n",
    "        for i in range(2, limit * 2 + 1):\n",
    "            min_move[i] += min_move[i-1]\n",
    "            ans = min(ans, min_move[i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(nums)\n",
    "        # changes = [0] * (2 * limit + 2)\n",
    "        \n",
    "        # for i in range(n // 2):\n",
    "        #     a, b = nums[i], nums[n - 1 - i]\n",
    "        #     #在[2,limit+2]范围内，有的范围要修改0，有的范围要修改1，其余范围要修改2。那么先初始化为都修改2次，到时候1次、0次再调整就好\n",
    "        #     left = 2\n",
    "        #     right = 2 * limit\n",
    "        #     changes[left] += 2\n",
    "        #     changes[right+1] -= 2\n",
    "        #     #在[1+min(a,b), limit+max(a,b)]范围内只需修改一次\n",
    "        #     left = 1 + min(a,b)\n",
    "        #     right = limit + max(a,b)\n",
    "        #     changes[left] -= 1 \n",
    "        #     changes[right+1] += 1\n",
    "        #     #在取得值为a+b时不用修改\n",
    "        #     left = a+b\n",
    "        #     right = a+b\n",
    "        #     changes[left] -= 1\n",
    "        #     changes[right+1] += 1\n",
    "\n",
    "        # # 计算累积和得到最小操作次数\n",
    "        # min_moves = n\n",
    "        # total = 0\n",
    "        # for i in range(2, 2*limit+1):\n",
    "        #     total += changes[i]\n",
    "        #     min_moves = min(min_moves, total)   \n",
    "        # return min_moves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        b = [0]*(2*limit+2)\n",
    "        k = len(nums)\n",
    "        for i in range(k//2):\n",
    "            l = i\n",
    "            r = k-1-i\n",
    "            b[2]+=2\n",
    "            b[1+min(nums[l],nums[r])] -=1\n",
    "            b[limit+max(nums[r],nums[l])+1]+=1\n",
    "            b[nums[r]+nums[l]] -=1\n",
    "            b[nums[r]+nums[l]+1] +=1\n",
    "        ans = 2*k\n",
    "        for i in range(2,2*limit+1):\n",
    "            b[i]+=b[i-1]\n",
    "            ans = min(ans,b[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        res, dp, n, mn = [0] * (2 * limit + 2), [0] * (2 * limit + 1), len(nums), 0\n",
    "        for i in range(n//2):\n",
    "            vi, vj = nums[i], nums[n-1-i]\n",
    "            if vi<vj: vi, vj = vj, vi\n",
    "            dp[vi+vj] -= 1\n",
    "            res[vj+1] -= 1\n",
    "            res[vi+limit+1] += 1\n",
    "        for i in range(1,2*limit+1):\n",
    "            res[i] += res[i-1]\n",
    "            mn = min(res[i] + dp[i], mn)\n",
    "        return mn + n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 1)\n",
    "        for i in range(len(nums) // 2):\n",
    "          diff[1] += 2\n",
    "          diff[min(nums[i], nums[-i-1])] -= 1\n",
    "          diff[nums[i] + nums[-i-1] - 1] -= 1\n",
    "          diff[nums[i] + nums[-i-1]] += 1\n",
    "          diff[max(nums[i], nums[-i-1]) + limit] += 1\n",
    "\n",
    "        for i in range(1, 2 * limit + 1):\n",
    "          diff[i] += diff[i-1]\n",
    "\n",
    "        return min(diff[1:-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 1)\n",
    "        for i in range(len(nums) // 2):\n",
    "          diff[1] += 2\n",
    "          diff[min(nums[i], nums[-i-1])] -= 1\n",
    "          diff[nums[i] + nums[-i-1] - 1] -= 1\n",
    "          diff[nums[i] + nums[-i-1]] += 1\n",
    "          diff[max(nums[i], nums[-i-1]) + limit] += 1\n",
    "\n",
    "        for i in range(1, 2 * limit + 1):\n",
    "          diff[i] += diff[i-1]\n",
    "\n",
    "        return min(diff[1:-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff = [0] * (2 * limit + 1)\n",
    "        for i in range(len(nums) // 2):\n",
    "          diff[1] += 2\n",
    "          diff[min(nums[i], nums[-i-1])] -= 1\n",
    "          diff[nums[i] + nums[-i-1] - 1] -= 1\n",
    "          diff[nums[i] + nums[-i-1]] += 1\n",
    "          diff[max(nums[i], nums[-i-1]) + limit] += 1\n",
    "\n",
    "        for i in range(1, 2 * limit + 1):\n",
    "          diff[i] += diff[i-1]\n",
    "\n",
    "        return min(diff[1:-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        moves = [0] * (2 * limit + 2)   # 和的取值范围是 [2, 2 * limit]\n",
    "        n = len(nums)\n",
    "        for i in range(n // 2):\n",
    "            a = nums[i]\n",
    "            b = nums[n - i - 1]\n",
    "            # 修改两次可以使得值变为 [2, 2 * limit] 中的任意值\n",
    "            moves[2] += 2\n",
    "            moves[2 * limit + 1] -= 2\n",
    "            # 修改 1 次可以使得值变为 [1 + min(a, b), limit + max(a, b)] 中的任意值\n",
    "            # 因为上面已经对 [2, 2 * limit] 这个范围的所有操作都加了 2, 所以要对上述范围中的操作数 -1\n",
    "            moves[1 + min(a, b)] -= 1\n",
    "            moves[limit + max(a, b) + 1] += 1\n",
    "            # 和改为 a + b 不需要修改任何值\n",
    "            moves[a + b] -= 1    \n",
    "            moves[a + b + 1] += 1\n",
    "        for i in range(2, 2 * limit + 1):\n",
    "            moves[i] = moves[i - 1] + moves[i]\n",
    "        return min(moves[2:-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        diff = [0]*(2*limit+2)\n",
    "        for i in range(n//2):\n",
    "            x, y = nums[i], nums[n-1-i]\n",
    "            low_1 = 1+x if x < y else 1+y\n",
    "            high_1 = limit+x if x > y else limit+y\n",
    "            if low_1 <= high_1:\n",
    "                diff[low_1] += 1\n",
    "                diff[high_1+1] -= 1\n",
    "            diff[x+y] -= 1\n",
    "            diff[x+y+1] += 1\n",
    "            \n",
    "            if 2 <= low_1-1:\n",
    "                diff[2] += 2\n",
    "                diff[low_1] -= 2\n",
    "            if high_1+1<=2*limit:\n",
    "                diff[high_1+1] += 2\n",
    "                diff[2*limit+1] -= 2\n",
    "        for i in range(1, 2*limit+2):\n",
    "            diff[i] += diff[i-1]\n",
    "        return min(diff[2:2*limit+1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        pairs = n // 2\n",
    "        res = []\n",
    "        for i in range(pairs):\n",
    "            res.append([nums[i], nums[n - i - 1]])\n",
    "        cnt = Counter([a + b for a, b in res])\n",
    "        left, right = sorted([min(a, b) + 1 for a, b in res]), sorted([max(a, b) + limit for a, b in res])\n",
    "        mi, mx = min(cnt.keys()), max(cnt.keys())\n",
    "        l, r = 0, 0\n",
    "        ans = inf\n",
    "        for i in range(mi, mx + 1):\n",
    "            # less = pairs - bisect_right(left, i)\n",
    "            # more = bisect_left(right, i)\n",
    "            while l < pairs and left[l] <= i:\n",
    "                l += 1\n",
    "            less = pairs - l \n",
    "            while r < pairs and right[r] < i:\n",
    "                r += 1\n",
    "            more = r \n",
    "            tmp = less + more + pairs - cnt[i]\n",
    "            ans = min(tmp, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        arr, diff = [0] * (2*limit + 1), [0] * (2*limit+1)\n",
    "        n = len(nums)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            a, b = nums[i], nums[j]\n",
    "            diff[2] += 2\n",
    "            diff[1 + min(a, b)] -= 2\n",
    "            diff[1 + min(a, b)] += 1\n",
    "            if limit + max(a, b) + 1 <= 2 * limit:\n",
    "                diff[limit + max(a, b) + 1] -= 1\n",
    "                diff[limit + max(a, b) + 1] += 2\n",
    "            diff[a + b] -= 1\n",
    "            if a + b + 1 <= 2 * limit:\n",
    "                diff[a + b + 1] += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        res = float(\"inf\")\n",
    "        for i in range(2, 2*limit+1):\n",
    "            arr[i] = arr[i-1] + diff[i]\n",
    "            res = min(res, arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = [0] * (2 * limit + 2)\n",
    "        diff = [0] * (2 * limit + 2)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            a, b = nums[i], nums[j]\n",
    "            diff[2] += 2\n",
    "            diff[1+min(a, b)] -= 2\n",
    "            diff[1+min(a, b)] += 1\n",
    "            diff[limit+max(a, b) + 1] -= 1\n",
    "            diff[limit+max(a, b) + 1] += 2\n",
    "            diff[2*limit+1] -= 2\n",
    "            diff[a+b] -= 1\n",
    "            diff[a+b+1] += 1\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(2, 2*limit+1):\n",
    "            res[i] = res[i-1] + diff[i]\n",
    "            ans = min(ans, res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        f = [0 for _ in range(2*limit+1+1)]       \n",
    "        n = len(nums)\n",
    "        # 注意差分效果是左闭右开\n",
    "        for i in range(n//2):\n",
    "            a,b = nums[i],nums[n-1-i]\n",
    "            t1,t2 = 2,min(a,b)\n",
    "            t3,t4 = min(a,b)+1,a+b-1 \n",
    "            t5,t6 = a+b+1,max(a,b)+limit \n",
    "            t7,t8 = max(a,b)+limit+1,2*limit \n",
    "            f[t1] += 2 \n",
    "            f[t2+1] -= 2 \n",
    "            f[t3] += 1 \n",
    "            f[t4+1] -= 1\n",
    "            f[t5] += 1 \n",
    "            f[t6+1] -= 1\n",
    "            f[t7] += 2\n",
    "            f[t8+1] -= 2      \n",
    "        acc = list(accumulate(f)) # 前缀和的pythonic写法\n",
    "        return min(acc[2:-1]) # 找target在2～2*limit的范围中，操作的最小值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        n = len(nums)\n",
    "        pairs = n // 2\n",
    "        res = []\n",
    "        for i in range(pairs):\n",
    "            res.append([nums[i], nums[n - i - 1]])\n",
    "        cnt = Counter([a + b for a, b in res])\n",
    "        left, right = sorted([min(a, b) + 1 for a, b in res]), sorted([max(a, b) + limit for a, b in res])\n",
    "        mi, mx = min(cnt.keys()), max(cnt.keys())\n",
    "        ans = inf\n",
    "        for i in range(mi, mx + 1):\n",
    "            less = pairs - bisect_right(left, i)\n",
    "            more = bisect_left(right, i)\n",
    "            tmp = (less + more) + pairs - cnt[i]\n",
    "            ans = min(tmp, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMoves(self, nums: List[int], limit: int) -> int:\n",
    "        diff=[0]*(limit*2+1)\n",
    "\n",
    "        n=len(nums)\n",
    "        for i in range(n//2):\n",
    "            a=nums[i]\n",
    "            b=nums[n-1-i]\n",
    "            diff[1]+=2\n",
    "            diff[limit*2]-=2\n",
    "            diff[min(a,b)]-=1\n",
    "            diff[limit+max(a,b)]+=1\n",
    "            diff[a+b-1]-=1\n",
    "            diff[a+b]+=1\n",
    "        return min(list(accumulate(diff[1:-1])))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
